package algorithm.graph.adjacencylist;

import java.util.Arrays;
import java.util.stream.IntStream;

public class UnionFindSet {
    int[] parentIdArray;

    public UnionFindSet(int length) {
        parentIdArray = IntStream.range(0, length).toArray();
    }

    public int findParentId(int index) {
        if (index != parentIdArray[index]) {
            parentIdArray[index] = findParentId(parentIdArray[index]);
        }
        return parentIdArray[index];
    }

    public int getGroupSize() {
        return Arrays.stream(parentIdArray).distinct().map(it -> 1).sum();
    }

    public void merge(int x, int y) {
        int parentIdX = this.findParentId(x);
        int parentIdY = this.findParentId(y);
        if (parentIdX < parentIdY) {
            parentIdArray[parentIdY] = parentIdX;
        } else {
            parentIdArray[parentIdX] = parentIdY;
        }
    }
}
